Relaxed Data Consistency Model

Data consistency#

In a distributed file system, we keep multiple copies/replicas of file data for availability purposes. If such systems allow data mutations, then data inconsistencies among replicas tend to appear for various reasons. For example, a node failure causes a mutation to fail on one of the replicas, making the data inconsistent among replicas; one replica will contain stale data while others have been updated. Clients reading data from multiple replicas will get different data, which can have consequences depending on the specific use case. Therefore, the file system that allows mutations should ensure data consistency.

If we have data that is consistent among all replicas, we can still face another problem due to concurrent writes on the same region. Since the file system allows multiple writers to write on the same region, the file region may mix data from multiple writes. Therefore, a file system should handle all these cases and provide its users with some guarantees so that the users don't see unexpected results. We can think of implementing a strong consistency model here to make the data consistent among all replicas. However, our system has to serve many requests at a time, and a system that provides strong consistency might compromise the system's performance. We need to provide consistency with good scalability and good performance. GFS's data consistency model is one of the most involved parts of the system. This increases its difficulty level. In this lesson, we will see what data consistency guarantees GFS offers its users and how it meets all their requirements. Before this, we need to know about the possible states of a file region after data mutation. Let's define these states first.

States of a file region after data mutation#

The state of a file region can be consistent or inconsistent, and defined or undefined after a data mutation.

• Consistent: A file region is consistent if a client sees the same data on all replicas after a mutation. In the illustration below, the left part shows that all the replicas have the same data. Thus, the clients reading from any of the replicas will read the same data.

• Inconsistent: A file region is inconsistent if a client sees different data on multiple replicas. In the illustration below, the right part shows that one of the replicas has different data than the other two. A client reading the same file region from three replicas will find different data.

Note: By definition, a defined region is a stronger condition than a consistent one. If a region is defined, it means that it is also consistent. Due to contrapositive, if a region is inconsistent, then it is undefined as well. A consistent region doesn't imply that it is defined; it can be undefined as well.

In symbols:

$defined \Rightarrow consistent \newline \newline inconsistent \Rightarrow undefined \newline consistent \nRightarrow defined$

Consistency assurance by GFS#

The specific state of a file region depends on the type of mutation (write/append). It also depends on how the system carries out the mutations (serial/concurrent) on that region, and whether the mutations result–in success or failure. Success ensures that the data is consistent among all replicas, while failure (except the ack failure where the mutation is actually done on all replicas but the reply from any of the replicas is lost) makes the file region inconsistent among replicas. A successful mutation includes retries by the client in case of failure on any replicas. The defined or undefined regions come out as a result of serial or concurrent executions of mutations.

The following table shows the state of the file region against different types of mutations and how each type of mutation was carried out by the system.

Random write#

1. Serial success: The serial success of random write operations ensures that the region is defined and, therefore, consistent. A write on the same region actually overwrites the data in that region. If these operations are executed in a sequence on each replica, each write operation overwrites the data written by the previous write operation, and at the end, the region contains the complete data written by the last write operation. The successful serial execution of random writes will leave the region defined and, by implication, consistent. It is important to note that, in case of a failure on any of the replicas, the successful execution of an operation involves a limited number of retries by the GFS client. Retrying the operation will apply the mutation on all replicas, including those that had already applied the write on them. Since a write operation on a region overwrites what was already written, the retry won’t cause any inconsistency among replicas.

2. Concurrent success: The concurrent success of random write operations on a region results in a consistent but potentially undefined region. This is because one write operation can interrupt the other, resulting in mingled fragments from multiple writes. An example is shown in the section above, states of a file region after data mutation, where we described an undefined region.

3. Failure: The failure of serial or concurrent random write operations results in inconsistent data among multiple replicas.

Record append#

Both the serial or concurrent success of record append operations result in defined regions interspersed with inconsistent regions.

3. Failure: The failure of serial or concurrent record append operations results in inconsistent data among multiple replicas.

Summary#

In this lesson, we’ve covered how GFS guarantees data consistency. GFS doesn't provide a strong consistency model to achieve good performance and scalability for client operations. It provides the clients with a relaxed consistency model. The guarantees are provided in terms of defined, undefined, consistent, and inconsistent regions based on the type of operation performed on a file region. These guarantees show that GFS is more suitable for append operations. So, GFS is a good solution for applications that append data to files, like logging systems, web crawlers, MapReduce, etc.

Since GFS provides different consistency guarantees for different operations, it depends on the applications to use GFS and deal with inconsistencies and undefined regions if they choose to use the operations that cause these issues. Some inconsistencies have to be handled by the GFS itself and the rest is on the applications that use it. We’ll look into how GFS or the applications deal with data inconsistency issues in the next lesson.